package com.yan_jiu_sheng.daily.AC;

import java.util.Arrays;
import java.util.Comparator;

/**
 * https://leetcode.cn/problems/minimum-rectangles-to-cover-points/description/?envType=daily-question&envId=2024-07-31
 * 排序贪心
 * 自我AC
 *
 * @author yulongtian
 * @create 2024-07-31 13:40
 */
public class Test20240731 {
    public static void main(String[] args) {
        // [[1, 0], [1, 4], [1, 8], [2, 1], [3, 5], [4, 6]]
//        int[][] points = {{2, 1}, {1, 0}, {1, 4}, {1, 8}, {3, 5}, {4, 6}};
//        int[][] points = {{0, 0}, {1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}, {6, 6}};
        int[][] points = {{2, 3}, {1, 2}};
        int w = 0;
        System.out.println(new Test20240731().minRectanglesToCoverPoints(points, w));
    }

    public int minRectanglesToCoverPoints(int[][] points, int w) {
        Arrays.sort(points, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        int cnt = 0;
        for (int i = 0; i < points.length; ) {
            int start = points[i][0];
            int end = start + w;
            while (true) {
                if (i >= points.length) {
                    cnt++;
                    break;
                }
                if (start <= points[i][0] && end >= points[i][0]) {
                    i++;
                } else {
                    cnt++;
                    break;
                }
            }
        }

        return cnt;
    }

}
